Computer systems (e.g., software, hardware, and their interconnection) must be trusted to a high degree in order for them to be used in critical and sensitive computations. Most computing platforms, however, are relatively devoid of protections against malicious attacks where, in particular, resident software is modified or reconfigured. Although software clients can, and arguably should, be protected with special security hardware (e.g., with cryptographic chips), they usually are not due to material costs and the additional engineering complexities they impose. In addition, for systems that are already deployed in the field, an integrity scheme based on software is the only option.
A number of challenge-response schemes have been proposed to determine and monitor the integrity of software subsystems in a distributed hardware/software environment. For example, a number of challenge-response schemes have been proposed to protect mobile phone clients communicating with hosts in wireless telephony networks. A user of a mobile phone can modify the software of the mobile phone. Thus, when the phone interacts inside a wireless network, the host components that communicate with the phone client may unknowingly interact with malicious code. Such code could be used to capture client information or present invalid or deceptive information to the host. Most proposed challenge-response schemes have focused on security mechanisms and policies that determine whether the requests issued by the mobile code should be allowed or denied by the (remote) host executing the code.
Another body of work considers the case of malicious hosts. For example, Esparza et al., “Limiting the Execution Time in a Host: A Way of Protecting Mobile Agents,” IEEE Sarnoff Symposium on Advances in Wired and Wireless Communications (2003), proposed using the execution time of an agent to detect possible malicious behavior by the host in order to protect the agent against abuses from a malicious host. Specifically, each host is required to save the agent's arrival and departing time. When the agent returns to the host of origin, a set of checks verifies that no host spent more time than expected executing the agent; if some host exceeds the time bound, then it is considered suspicious of malicious behavior.
Kennell and Jamieson, “Establishing the Genuinity of Remote Computer Systems,” 12th USNIX Security Symposium, 295-310 (2003), suggested sending a challenge problem to a machine in order to verify that the machine is running the correct version of uncorrupted software (specifically, a kernel). In this system, referred to as “Genuity,” the challenge problem is essentially a checksum (i.e., a one-byte sum) of the contents of pseudo-random memory addresses. The challenge may also incorporate other hardware-specific values into the checksum. The trusted host preparing the challenge problem also computes the checksum, and if the host being tested calculates the same checksum as the trusted host and returns it “quickly enough,” the host is considered genuine, since it is assumed that there would be no fast simulation.
While such challenge-response schemes based on an evaluation of the execution time of a known function provide an effective basis for detecting malicious behavior, they suffer from a number of limitations, which if overcome, could greatly improve the security of and integrity of software subsystems in a distributed hardware/software environment. For example, the Genuity system relies on only one type of function for verifying the integrity of clients. Thus, an adversary can more easily predict the type of function to expect. A need therefore exists for a challenge-response scheme that employs a number of different functions, thereby making it more difficult to predict the functionality of the agents and making such integrity protection stronger.